﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 图解算法数据结构._59_MaxQueue
{
    public class MyCircularDeque
    {
        private int[] dataset;
        public int MaxSize { get; }
        private int pFront;
        private int pRear;
        public int Length { get; private set; }
        /** Initialize your data structure here. Set the size of the deque to be k. */
        public MyCircularDeque(int k)
        {
            MaxSize = k;
            dataset = new int[MaxSize];
            pFront = 0;
            pRear = 0;
            Length = 0;
        }

        /** Adds an item at the front of Deque. Return true if the operation is successful. */
        public bool InsertFront(int value)
        {
            if (Length == MaxSize)
                return false;
            pFront--;
            pFront = (pFront + MaxSize) % MaxSize;
            dataset[pFront] = value;
            Length++;
            return true;
        }

        /** Adds an item at the rear of Deque. Return true if the operation is successful. */
        public bool InsertLast(int value)
        {
            if (Length == MaxSize)
                return false;
            dataset[pRear] = value;
            pRear = (pRear + 1) % MaxSize;
            Length++;
            return true;
        }

        /** Deletes an item from the front of Deque. Return true if the operation is successful. */
        public bool DeleteFront()
        {
            if (Length == 0)
                return false;
            pFront = (pFront + 1) % MaxSize;
            Length--;
            return true;
        }

        /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
        public bool DeleteLast()
        {
            if (Length == 0)
                return false;
            pRear--;
            pRear = (pRear + MaxSize) % MaxSize;
            Length--;
            return true;
        }

        /** Get the front item from the deque. */
        public int GetFront()
        {
            if (Length == 0)
                return -1;
            return dataset[pFront];
        }

        /** Get the last item from the deque. */
        public int GetRear()
        {
            if (Length == 0)
                return -1;
            return dataset[(pRear - 1 + MaxSize) % MaxSize];
        }

        /** Checks whether the circular deque is empty or not. */
        public bool IsEmpty()
        {
            return Length == 0 ? true : false;
        }

        /** Checks whether the circular deque is full or not. */
        public bool IsFull()
        {
            return Length == MaxSize ? true : false;
        }
    }


    class MainProject
    {
        static void Main(string[] args)
        {
            //Console.WriteLine(MaxSlidingWindow(new int[] { 1, 3, -1, -3, 5, 3, 6, 7 }, 3));

            MaxQueue maxQueue = new MaxQueue();
            int val1 = maxQueue.Max_value();
            maxQueue.Pop_front();
            int val2 = maxQueue.Max_value();

            maxQueue.Push_back(1);
            maxQueue.Push_back(2);
            int val = maxQueue.Max_value();
            maxQueue.Pop_front();
            int val12 = maxQueue.Max_value();

    
            Console.ReadKey();
        }

        public class MaxQueue
        {
            MyCircularDeque drabQue = new MyCircularDeque(1000);
            Queue<int> que = new Queue<int>();
            public MaxQueue()
            {

            }

            public int Max_value()
            {
                return drabQue.Length == 0 ? -1 : drabQue.GetFront();
            }

            public void Push_back(int value)
            {
                while (drabQue.Length != 0 && drabQue.GetRear()<value)
                {
                    drabQue.DeleteLast();
                }
                drabQue.InsertLast(value);
                que.Enqueue(value);
            }

            public int Pop_front()
            {
                if (que.Count == 0) return -1;
                int retVal = -1;
                if (que.Peek()== drabQue.GetFront()) drabQue.DeleteFront();
                retVal = que.Dequeue();
                return retVal;
            }
        }
    }
}
